package leetcode

import (
	"container/heap"
)

//优先级队列保存保质期快过期的苹果，每次先吃
func eatenApples(apples []int, days []int) int {
	var hps pairs
	res := 0
	i := 0
	//果树产果的时候
	for ; i < len(apples); i++ {
		//先取出过期了的食品
		for len(hps) > 0 && hps[0].dayExpired <= i {
			heap.Pop(&hps)
		}
		//如果还有苹果，就添加进去
		if apples[i]>0{
			heap.Push(&hps, pair{i + days[i], apples[i]})
		}
		//先吃快过期的苹果
		if len(hps)>0{
			hps[0].appNum--
			//苹果吃完了就撇出来
			if hps[0].appNum==0{
				heap.Pop(&hps)
			}
			//吃苹果咯
			res++
		}
	}
	//果树不产果了
	for len(hps)>0{
		//取出快过期的
		for len(hps) > 0 && hps[0].dayExpired <= i {
			heap.Pop(&hps)
		}
		if len(hps)==0{
			return res
		}
		hps[0].appNum--
		//苹果吃完了就撇出来
		if hps[0].appNum==0{
			heap.Pop(&hps)
		}
		i++
		//吃苹果咯
		res++
	}
	return res
}

type pair struct {
	dayExpired, appNum int
}
type pairs []pair

func (t pairs) Len() int {
	return len(t) //
}

func (t pairs) Less(i, j int) bool {
	return t[i].dayExpired < t[j].dayExpired
}

func (t pairs) Swap(i, j int) {
	t[i], t[j] = t[j], t[i]
}

func (t *pairs) Push(x interface{}) {
	*t = append(*t, x.(pair))
}

func (t *pairs) Pop() interface{} {
	n := len(*t)
	x := (*t)[n-1]
	*t = (*t)[:n-1]
	return x
}
